import java.util.*;

/**
 * @author LI DUO
 * @version 1.0
 * @date 2019/10/27 上午 10:16
 */
public class day1911 {

    interface CustomFunction {
        // Returns f(x, y) for any given positive integers x and y.
        // Note that f(x, y) is increasing with respect to both x and y.
        // i.e. f(x, y) < f(x + 1, y), f(x, y) < f(x, y + 1)
        public int f(int x, int y);
    }

    ;

    static class day191027 {

        Set<Integer> visited = new HashSet<>();
        List<Integer> res = new ArrayList<>();

        public List<Integer> circularPermutation(int n, int start) {
            res.add(start);
            visited.add(start);
            dfs(n, start);
            return res;
        }

        boolean dfs(int n, int cur) {
            if (res.size() == (1 << n)) {
                int tmp = res.get(0) ^ res.get(res.size() - 1);
                return (tmp & (tmp - 1)) == 0;
            }
            for (int i = 0; i < n; i++) {
                int other = cur ^ (1 << i);
                if (!visited.contains(other)) {
                    visited.add(other);
                    res.add(other);
                    if (dfs(n, other)) {
                        return true;
                    }
                    visited.remove(other);
                    res.remove(res.size() - 1);
                }
            }
            return false;
        }

        public List<List<Integer>> findSolution(CustomFunction customfunction, int z) {
            List<List<Integer>> ret = new ArrayList<>();
            for (int x = 1; x <= z; x++) {
                for (int y = 1; y <= z; y++) {
                    if (customfunction.f(x, y) == z) {
                        if (!ret.contains(Arrays.asList(x, y))) {
                            ret.add(Arrays.asList(x, y));
                        }
                    }
                }
            }
            return ret;
        }

        public int maxLength(List<String> arr) {
            int maxL = 0;
            int index = 0;
            Collections.sort(arr);
            HashSet<Character> maxLSet = new HashSet<>();
            for (int in = arr.size() - 1; in >= 0; in--) {
                String s = arr.get(in);
                HashSet<Character> hashSet = new HashSet<>();
                for (int i = 0; i < s.length(); i++) {
                    if (hashSet.contains(s.charAt(i))) {
                        break;
                    }
                    hashSet.add(s.charAt(i));
                }
                if (hashSet.size() == s.length()) {
                    if (s.length() > maxL) {
                        index = in;
                        maxL = hashSet.size();
                        maxLSet = hashSet;
                    }
                }
            }
            for (int i = arr.size() - 1; i >= 0; i--) {
                if (i == index) {
                    continue;
                }
                HashSet<Character> hashSet = new HashSet<>(maxLSet);
                String s = arr.get(i);
                for (int j = 0; j < s.length(); j++) {
                    if (hashSet.contains(s.charAt(j))) {
                        break;
                    }
                    hashSet.add(s.charAt(j));
                }
                if (hashSet.size() == (s.length() + maxLSet.size())) {
                    if (hashSet.size() > maxL) {
                        maxL = hashSet.size();
                        maxLSet = hashSet;
                    }
                }
            }
            return maxL;
        }

        public int maxLength2(List<String> arr) {
            int n = arr.size();
            int res = 0;
            for (int set = 0; set < (1 << n); set++) {
                boolean ok = true;
                Set<Character> have = new HashSet<>();
                for (int i = 0; i < n; i++) {
                    if ((set & (1 << i)) > 0) {
                        for (int j = 0; j < arr.get(i).length(); j++) {
                            if (have.contains(arr.get(i).charAt(j))) {
                                ok = false;
                                break;
                            } else {
                                have.add(arr.get(i).charAt(j));
                            }
                        }
                    }
                }
                if (ok) {
                    res = Math.max(res, have.size());
                }
            }
            return res;
        }

        public int tilingRectangle(int n, int m) {
            int[] a1 = {1};
            int[] a2 = {2, 1};
            int[] a3 = {3, 3, 1};
            int[] a4 = {4, 2, 4, 1};
            int[] a5 = {5, 4, 4, 5, 1};
            int[] a6 = {6, 3, 2, 3, 5, 1};
            int[] a7 = {7, 5, 5, 5, 5, 5, 1};
            int[] a8 = {8, 4, 5, 2, 5, 4, 7, 1};
            int[] a9 = {9, 6, 3, 6, 6, 3, 6, 7, 1};
            int[] a10 = {10, 5, 6, 4, 2, 4, 6, 5, 6, 1};
            int[] a11 = {11, 7, 6, 6, 6, 6, 6, 6, 7, 6, 1};
            int[] a12 = {12, 6, 4, 3, 6, 2, 6, 3, 4, 5, 7, 1};
            int[] a13 = {13, 8, 7, 7, 6, 6, 6, 6, 7, 7, 6, 7, 1};

            int[][] a = {a1, a2, a3, a4, a5, a6, a7, a8, a9, a10, a11, a12, a13};
            int mx = Math.max(n, m) - 1;
            int mi = Math.min(n, m) - 1;

            return a[mx][mi];
        }

        public int tilingRectangle2(int n, int m) {
            int[][] dp = new int[15][15];
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= m; j++) {
                    dp[i][j] = i == j ? 1 : i * j;
                    for (int p = 1; p < i; p++) {
                        dp[i][j] = Math.min(dp[i][j], dp[p][j] + dp[i - p][j]);
                    }
                    for (int p = 1; p < j; p++) {
                        dp[i][j] = Math.min(dp[i][j], dp[i][p] + dp[i][j - p]);
                    }
                    for (int x = 2; x < i; x++) {
                        for (int y = 2; y < j; y++) {
                            dp[i][j] = Math.min(dp[i][j], dp[x - 1][y] + dp[x][j - y] + dp[i - x + 1][y - 1] + dp[i - x][j - y + 1] + 1);
                        }
                    }
                }
            }
            return dp[n][m];
        }

        /**
         * next ^= next ^ (next - 1) + 1
         *
         * @param n
         * @param start
         * @return
         */
        public List<Integer> circularPermutation2(int n, int start) {
            List<Integer> ret = new ArrayList<>(1 << n);
            int[] res = new int[1 << n];
            res[0] = start;
            for (int i = 1; i <= n; i++) {
                int size = 1 << i;
                int mask = 1 << (i - 1);
                for (int j = 0; j < mask; j++) {
                    res[size - 1 - j] = res[j] ^ mask;
                    System.out.println(res[size - 1 - j]);
                }
            }
            for (int re : res) {
                ret.add(re);
            }
            return ret;
        }
    }

    static class day191029 {

        public int[] rearrangeBarcodes(int[] barcodes) {
            if (barcodes.length < 2) {
                return barcodes;
            }
            int[] ret = new int[barcodes.length];
            int[] count = new int[10001];
            for (int barcode : barcodes) {
                count[barcode]++;
            }

            int maxCnt = 0, maxNum = 0;
            for (int i = 0; i < count.length; i++) {
                if (count[i] > maxCnt) {
                    maxCnt = count[i];
                    maxNum = i;
                }
            }

            int pos = 0, index = 0;
            while (pos < barcodes.length) {
                if (count[maxNum] <= 0) {
                    break;
                } else {
                    ret[pos] = maxNum;
                    count[maxNum]--;
                    pos += 2;
                }
            }

            while (pos < barcodes.length) {
                if (count[index] <= 0) {
                    index++;
                } else {
                    ret[pos] = index;
                    count[index]--;
                    pos += 2;
                }
            }

            pos = 1;
            while (pos < barcodes.length) {
                if (count[index] <= 0) {
                    index++;
                } else {
                    ret[pos] = index;
                    count[index]--;
                    pos += 2;
                }
            }

            return ret;
        }

        public int[] rearrangeBarcodes2(int[] barcodes) {
            /* 存在特殊情况结果类似 2, 1, 2, 1, 2
             * 因此优先使用出现次数最多的元素填充奇数位
             */
            /* 统计每个数据的出现次数 */
            int len = barcodes.length;
            int[] count = new int[10001];
            for (int i = 0; i < len; i++) {
                count[barcodes[i]]++;
            }
            /* 得到出现次数最多的数字 */
            int maxCnt = 0;
            int maxNum = 0;
            for (int i = 1; i < 10001; i++) {
                if (count[i] > maxCnt) {
                    maxCnt = count[i];
                    maxNum = i;
                }
            }
            /* 先填充奇数位 */
            int[] result = new int[len];
            int pos = 0;    // result 填充位置
            int idx = 0;    // count 使用位置
            /* 先使用出现次数最多的数字填充奇数位, 最多恰好填满 */
            while (pos < len) {
                if (count[maxNum] <= 0) {
                    break;  // 填充完毕
                } else {
                    count[maxNum]--;
                    result[pos] = maxNum;
                    pos += 2;
                }
            }
            /* 尝试继续填充奇数位 */
            while (pos < len) {
                if (count[idx] <= 0) {
                    idx++;
                } else {
                    count[idx]--;
                    result[pos] = idx;
                    pos += 2;
                }
            }
            /* 继续填充偶数位 */
            pos = 1;
            while (pos < len) {
                if (count[idx] <= 0) {
                    idx++;
                } else {
                    count[idx]--;
                    result[pos] = idx;
                    pos += 2;
                }
            }
            return result;

        }

    }

    static class day191030 {

        public int longestCommonSubsequence(String text1, String text2) {
            int[][] dp = new int[text1.length()][text2.length()];
            for (int i = 0; i < text1.length(); i++) {
                if (text1.charAt(i) == text2.charAt(0)) {
                    dp[i][0] = 1;
                } else if (i != 0) {
                    dp[i][0] = dp[i - 1][0];
                } else {
                    dp[i][0] = 0;
                }
            }
            for (int i = 0; i < text2.length(); i++) {
                if (text1.charAt(0) == text2.charAt(i)) {
                    dp[0][i] = 1;
                } else if (i != 0) {
                    dp[0][i] = dp[0][i - 1];
                } else {
                    dp[i][0] = 0;
                }
            }
            for (int i = 1; i < text1.length(); i++) {
                for (int j = 1; j < text2.length(); j++) {
                    if (text1.charAt(i) == text2.charAt(j)) {
                        dp[i][j] = Math.max(dp[i - 1][j - 1] + 1, Math.max(dp[i - 1][j], dp[i][j - 1]));
                    } else {
                        dp[i][j] = Math.max(dp[i - 1][j - 1], Math.max(dp[i - 1][j], dp[i][j - 1]));
                    }
                }
            }
            return dp[text1.length() - 1][text2.length() - 1];
        }

        /**
         * [1,0,2,3,0,4,5,0]
         * [1,0,0,2,3,0,0,4]
         *
         * @param arr
         */
        public void duplicateZeros(int[] arr) {
            for (int i = 0; i < arr.length; i++) {
                if (arr[i] == 0) {
                    if (i + 1 < arr.length) {
                        int temp = arr[i + 1];
                        arr[i + 1] = 0;
                        int j = i + 2;
                        int next;
                        while (j < arr.length) {
                            next = arr[j];
                            arr[j] = temp;
                            temp = next;
                            j++;
                        }
                        i++;
                    }
                }
            }
        }

        public int shortestPathBinaryMatrix(int[][] grid) {
            int[][] state = new int[grid.length][grid.length];
            Queue<Integer> queue = new LinkedList<>();
            if (grid[0][0] == 1) {
                return -1;
            }
            if (grid.length == 1) {
                return 1;
            }
            //初始状态
            state[0][0] = 1;
            queue.add(0);
            //定义八个方向
            int[][] direction = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
            while (!queue.isEmpty()) {
                Integer tmp = queue.poll();
                int row = tmp / grid.length;
                int col = tmp % grid.length;

                for (int[] dir : direction) {
                    int newRow = dir[0] + row;
                    int newCol = dir[1] + col;
                    if (newRow >= 0 && newRow < grid.length && newCol >= 0 && newCol < grid.length && grid[newRow][newCol] == 0 && state[newRow][newCol] == 0) {
                        state[newRow][newCol] = state[row][col] + 1;
                        queue.add(grid.length * newRow + newCol);

                        if (newRow == grid.length - 1 && newCol == grid.length - 1) {
                            return state[newRow][newCol];
                        }
                    }
                }
            }
            return -1;
        }

        public String shortestCommonSupersequence(String str1, String str2) {
            int[][] dp = new int[str1.length() + 1][str2.length() + 1];
            StringBuilder result = new StringBuilder();
            for (int i = 1; i <= str1.length(); i++) {
                for (int j = 1; j <= str2.length(); j++) {
                    if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                        dp[i][j] = Math.max(dp[i - 1][j - 1] + 1, Math.max(dp[i - 1][j], dp[i][j - 1]));
                    } else {
                        dp[i][j] = Math.max(dp[i - 1][j - 1], Math.max(dp[i - 1][j], dp[i][j - 1]));
                    }
                }
            }

            //构造lcd
            StringBuilder lcds = new StringBuilder();

            int lcd = dp[str1.length()][str2.length()];

            int i = str1.length();
            int j = str2.length();

            while (lcd > 0) {
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    //list.add(String.valueOf(str1.charAt(i-1)));
                    lcds.append(str1.charAt(i - 1));
                    lcd--;
                    i--;
                    j--;
                } else {
                    if (dp[i - 1][j] == lcd) {
                        i--;
                    } else {
                        j--;
                    }
                }
            }
            lcds.reverse();

            //构造结果

            int p1 = 0, p2 = 0;

            for (int k = 0; k < lcds.length(); k++) {
                for (i = p1; i < str1.length(); i++) {
                    if (str1.charAt(i) == lcds.charAt(k)) {
                        break;
                    }
                }
                for (j = p2; j < str2.length(); j++) {
                    if (str2.charAt(j) == lcds.charAt(k)) {
                        break;
                    }
                }

                result.append(str1, p1, i).append(str2, p2, j + 1);
                p1 = i + 1;
                p2 = j + 1;
            }
            result.append(str1.substring(p1)).append(str2.substring(p2));
            return result.toString();
        }
    }

    static class day191101 {

        public double nthPersonGetsNthSeat(int n) {
            double[] dp = new double[n + 1];
            dp[1] = 1;
            for (int i = 2; i <= n; i++) {
                dp[i] = (1 + (i - 2) * dp[i - 1]) / i;
            }
            return dp[n];
        }

    }

    static class day191104 {

        public int minimumSwap(String s1, String s2) {
            int c1 = 0, c2 = 0;
            for (int i = 0; i < s1.length(); i++) {
                if (s1.charAt(i) == 'x' && s2.charAt(i) == 'y') {
                    c1++;
                }
                if (s1.charAt(i) == 'y' && s2.charAt(i) == 'x') {
                    c2++;
                }
            }
            if (c1 % 2 + c2 % 2 == 1) {
                return -1;
            }
            int ret = c1 / 2 + c2 / 2;
            if (c1 % 2 == 1) {
                ret += 2;
            }
            return ret;
        }

        public String minRemoveToMakeValid(String s) {
            Stack<Integer> stack = new Stack<>();
            boolean[] flag = new boolean[s.length()];
            for (int i = 0; i < s.length(); i++) {
                if (s.charAt(i) == '(') {
                    stack.add(i);
                } else if (s.charAt(i) == ')') {
                    if (stack.empty()) {
                        continue;
                    }
                    flag[i] = true;
                    flag[stack.pop()] = true;
                }
            }
            StringBuilder builder = new StringBuilder();
            for (int i = 0; i < s.length(); i++) {
                if (s.charAt(i) == '(' || s.charAt(i) == ')') {
                    if (flag[i]) {
                        builder.append(s.charAt(i));
                    }
                } else {
                    builder.append(s.charAt(i));
                }
            }
            return builder.toString();
        }

        public int numberOfSubarrays(int[] nums, int k) {
            int s = 0, ret = 0;
            Map<Integer, Integer> map = new HashMap<>();
            map.put(s, 1);
            for (int num : nums) {
                if (num % 2 == 1) {
                    s++;
                }
                if (s - k >= 0) {
                    ret += map.getOrDefault(s - k, 0);
                }
                map.put(s, map.getOrDefault(s, 0) + 1);
            }
            return ret;
        }

        /**
         * 贴个定理链接：https://baike.baidu.com/item/裴蜀定理/5186593
         * <p>
         * 因此我们只需要计算数组所有数的最大公约数是否等于1即可
         *
         * @param nums
         * @return
         */
        public boolean isGoodArray(int[] nums) {
            int ret = nums[0];
            for (int i = 1; i < nums.length; i++) {
                ret = gcd(ret, nums[i]);
            }
            return ret == 1;
        }

        private int gcd(int x, int y) {
            if (y == 0) {
                return x;
            } else {
                return gcd(y, x % y);
            }
        }

    }

    static class day191107 {
        public int wiggleMaxLength(int[] nums) {
            if (nums.length < 2) {
                return nums.length;
            }
            return 1 + Math.max(calculated(nums, 0, true), calculated(nums, 0, false));
        }

        private int calculated(int[] nums, int i, boolean isUp) {
            int maxCount = 0;
            for (int j = i + 1; j < nums.length; j++) {
                if ((nums[j] > nums[i] && isUp) || (nums[j] < nums[i] && !isUp)) {
                    maxCount = Math.max(maxCount, calculated(nums, j, !isUp) + 1);
                }
            }
            return maxCount;
        }

        public int wiggleMaxLength2(int[] nums) {
            if (nums.length < 2) {
                return nums.length;
            }
            int[] up = new int[nums.length];
            int[] down = new int[nums.length];
            up[0] = down[0] = 1;
            for (int i = 1; i < nums.length; i++) {
                if (nums[i - 1] < nums[i]) {
                    up[i] = down[i - 1] + 1;
                    down[i] = down[i - 1];
                } else if (nums[i - 1] > nums[i]) {
                    down[i] = up[i - 1] + 1;
                    up[i] = up[i - 1];
                } else {
                    up[i] = up[i - 1];
                    down[i] = down[i - 1];
                }
            }
            return Math.max(up[nums.length - 1], down[nums.length - 1]);
        }

        public int wiggleMaxLength3(int[] nums) {
            if (nums.length < 2) {
                return nums.length;
            }
            int up = 1, down = 1;
            for (int i = 1; i < nums.length; i++) {
                if (nums[i - 1] < nums[i]) {
                    up = down + 1;
                } else if (nums[i - 1] > nums[i]) {
                    down = up + 1;
                }
            }
            return Math.max(up, down);
        }
    }

    static class day191108 {

        private Set<String> set = new HashSet<>();

        public int combinationSum4(int[] nums, int target) {
            for (int i = 0; i < nums.length; i++) {
                List<Integer> list = new ArrayList<>();
                list.add(nums[i]);
                getSum(nums, nums[i], target, list);
            }
            return set.size();
        }

        private void getSum(int[] nums, int sum, int target, List<Integer> list) {
            if (set.contains(Arrays.toString(list.toArray()))) {
                list.remove(list.size() - 1);
                return;
            }
            if (sum == target) {
                set.add(Arrays.toString(list.toArray()));
                list.remove(list.size() - 1);
                return;
            }
            if (sum > target) {
                list.remove(list.size() - 1);
                return;
            }
            for (int i = 0; i < nums.length; i++) {
                list.add(nums[i]);
                if (set.contains(Arrays.toString(list.toArray()))) {
                    continue;
                }
                getSum(nums, nums[i] + sum, target, list);
            }
            list.remove(list.size() - 1);
        }

        private int[] mem;

        public int combinationSum42(int[] nums, int target) {
            mem = new int[target + 1];
            Arrays.fill(mem, -1);
            mem[0] = 1;
            return findSum(nums, target);
        }

        private int findSum(int[] nums, int target) {
            if (mem[target] != -1) {
                return mem[target];
            }
            int res = 0;
            for (int num : nums) {
                if (target > num) {
                    res += findSum(nums, target - num);
                }
            }
            mem[target] = res;
            return res;
        }


        public int combinationSum43(int[] nums, int target) {
            int[] dp = new int[target + 1];
            dp[0] = 1;
            for (int i = 0; i < target; i++) {
                for (int num : nums) {
                    if (i + num <= target) {
                        dp[i + num] += dp[i];
                    }
                }
            }
            return dp[target];
        }

        public boolean canPartition(int[] nums) {
            //动态规划，背包问题，从nums中选择一部分数字组合，填满容量为sum/2的背包
            int n = nums.length;
            if (n == 0) {
                return false;
            }
            //确定背包c的大小
            int sum = 0;
            for (int num : nums) {
                sum += num;
            }
            //两个相等的整数的和一定为偶数
            if (sum % 2 == 1) {
                return false;
            }
            int c = sum / 2;
            //动态规划
            //明确状态：dp[m][n] 考虑是否将第m个数字放入容量为n的背包
            boolean[][] dp = new boolean[n][c + 1];
            //状态初始化
            for (int i = 0; i <= c; i++) {
                dp[0][i] = i == nums[0];
            }
            //状态转移方程：dp[m][n] = dp[m-1][n] || dp[m-1][n-nums[m]]
            for (int i = 1; i < n; i++) {
                for (int j = 0; j <= c; j++) {
                    dp[i][j] = dp[i - 1][j];
                    if (nums[i] <= j) {
                        dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]];
                    }
                }
            }
            return dp[n - 1][c];
        }
    }

    static class day191110 {
        public List<List<Integer>> reconstructMatrix(int upper, int lower, int[] colsum) {
            List<List<Integer>> ret = new ArrayList<>();
            int sum = 0;
            for (int i : colsum) {
                sum += i;
            }
            if (sum != upper + lower) {
                return ret;
            }
            int[][] temp = new int[2][colsum.length];
            Arrays.fill(temp[0], -1);
            Arrays.fill(temp[1], -1);
            for (int i = 0; i < colsum.length; i++) {
                if (colsum[i] == 0) {
                    temp[0][i] = temp[1][i] = 0;
                } else if (colsum[i] == 2) {
                    upper--;
                    lower--;
                    temp[0][i] = temp[1][i] = 1;
                }
            }
            for (int i = 0; i < temp[0].length && upper > 0; i++) {
                if (temp[0][i] == -1) {
                    temp[0][i] = 1;
                    temp[1][i] = 0;
                    upper--;
                }
            }
            if (upper > 0) {
                return ret;
            }
            for (int i = 0; i < temp[1].length && lower > 0; i++) {
                if (temp[1][i] == -1) {
                    temp[1][i] = 1;
                    temp[0][i] = 0;
                    lower--;
                }
            }
            if (lower > 0) {
                return ret;
            }
            List<Integer> upperList = new ArrayList<>();
            List<Integer> lowerList = new ArrayList<>();
            for (int i = 0; i < temp[0].length; i++) {
                upperList.add(temp[0][i]);
            }
            for (int i = 0; i < temp[1].length; i++) {
                lowerList.add(temp[1][i]);
            }
            ret.add(upperList);
            ret.add(lowerList);
            return ret;
        }

        public int closedIsland(int[][] grid) {
            int island = 0;
            for (int i = 0; i < grid.length; i++) {
                for (int j = 0; j < grid[i].length; j++) {
                    //是陆地
                    if (grid[i][j] == 0) {
                        flag = true;
                        marked(grid, i, j);
                        if (i == 0 || i == grid.length - 1 || j == 0 || j == grid[0].length - 1) {
                            continue;
                        }
                        if (!flag) {
                            continue;
                        }
                        island++;
                    }
                    System.out.print(grid[i][j] + ",");
                }
                System.out.println();
            }
            return island;
        }

        private boolean flag;

        private void marked(int[][] grid, int i, int j) {
            if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] != 0) {
                return;
            }
            if (i == 0 || i == grid.length - 1 || j == 0 || j == grid[0].length - 1) {
                flag = false;
            }
            grid[i][j] = 2;
            //分别往 上 下 左 右 递归
            marked(grid, i + 1, j);
            marked(grid, i - 1, j);
            marked(grid, i, j - 1);
            marked(grid, i, j + 1);
        }

        public int oddCells(int n, int m, int[][] indices) {
            int[][] map = new int[n][m];
            for (int i = 0; i < indices.length; i++) {
                int col = indices[i][0];
                int row = indices[i][1];
                for (int j = 0; j < m; j++) {
                    map[col][j]++;
                }
                for (int j = 0; j < n; j++) {
                    map[j][row]++;
                }
            }
            int ret = 0;
            for (int[] ints : map) {
                for (int anInt : ints) {
                    if (anInt % 2 == 1) {
                        ret++;
                    }
                }
            }
            return ret;
        }

        public int maxScoreWords(String[] words, char[] letters, int[] score) {
            List<Character> list = new ArrayList<>();
            for (char letter : letters) {
                list.add(letter);
            }
            return maxScoreWords(words, list, score, 0);
        }

        private int maxScoreWords(String[] words, List<Character> list, int[] score, int i) {
            if (i == words.length) {
                return 0;
            }
            char[] charArray = words[i].toCharArray();
            List<Character> characters = new ArrayList<>(list);
            for (Character c : charArray) {
                if (!characters.remove(c)) {
                    return maxScoreWords(words, list, score, i + 1);
                }
            }
            int ret = 0;
            for (char c : charArray) {
                ret += score[c - 'a'];
            }
            return Math.max(ret + maxScoreWords(words, characters, score, i + 1), maxScoreWords(words, list, score, i + 1));
        }
    }

    static class day191112 {
        public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
            boolean[][] dp = new boolean[maxChoosableInteger][desiredTotal];

            return dp[maxChoosableInteger - 1][desiredTotal - 1];
        }

        public boolean CanIWin2(int maxChoosableInteger, int desiredTotal) {
            /*
             * 题目概述：给定可选择数字的范围，以及目标值，判断先手，是否稳赢
             *
             * 思路：
             *  1. 对弈的两个人都是高手，所以他俩的思考方式一定是一样的，因此对弈的过程，也可以看作是递归的过程，每次走步都为了更接近让自己赢得胜利的目标
             *  2. 稳赢的思考过程如下:
             *      2.1 在可选的数字中，我用最大的数字可以触及目标，那么自己就赢了
             *      2.2 自己怎么选都不可能触及目标的话，那么就寄希望于自己选择一个对方无法赢的数字，只要对方赢不了，那么就是自己赢了
             *
             * 关键点：
             *
             * 时间复杂度： O(n)，因为可选择的数字是有限的，n 个，所以肯定是在 n 轮之内结束的
             * 空间复杂度： O(n)
             */

            //若所有可能性的总和都无法触及目标值的话，先手也是不可能赢的了
            int sumTemp = (1 + maxChoosableInteger) * maxChoosableInteger / 2;
            if (sumTemp < desiredTotal) {
                return false;
            }

            return Recursive(0, maxChoosableInteger, desiredTotal, new HashMap<Integer, Boolean>());
        }

        private boolean Recursive(int status, int maxChoosableInteger, int desiredTotal, Map<Integer, Boolean> dic) {
            if (dic.containsKey(status)) {
                return dic.get(status);
            }

            boolean forReturn = false;
            for (int i = maxChoosableInteger; i >= 1; i--) {

                if (((status >> i) & 1) == 1) {
                    continue;
                }

                if (i >= desiredTotal) {
                    forReturn = true;
                } else {
                    int newSatus = status | (1 << i);
                    forReturn = !Recursive(newSatus, maxChoosableInteger, desiredTotal - i, dic);
                }

                if (forReturn) {
                    break;
                }
            }
            dic.put(status, forReturn);
            return forReturn;
        }
    }

    static class day191114 {
        public int findSubstringInWraproundString(String p) {
            if (p.length() == 0) {
                return 0;
            }
            int[] dp = new int[26];
            int maxLen = 1;
            for (int i = 0; i < p.length(); i++) {
                if (i > 0 && (p.charAt(i) - p.charAt(i - 1) == 1 || p.charAt(i - 1) - p.charAt(i) == 25)) {
                    maxLen++;
                } else {
                    maxLen = 1;
                }
                dp[p.charAt(i) - 'a'] = Math.max(dp[p.charAt(i) - 'a'], maxLen);
            }
            int ret = 0;
            for (int i : dp) {
                ret += i;
            }
            return ret;
        }
    }

    static class day191115 {
        public int findMaxForm(String[] strs, int m, int n) {
            if (strs.length == 0) {
                return 0;
            }
            int[][] dp = new int[m + 1][n + 1];
            for (String str : strs) {
                int zero = 0, one = 0;
                for (int i = 0; i < str.length(); i++) {
                    if (str.charAt(i) == '0') {
                        zero++;
                    } else {
                        one++;
                    }
                }
                for (int i = m; i >= zero; i--) {
                    for (int j = n; j >= one; j--) {
                        dp[i][j] = Math.max(dp[i][j], dp[i - zero][j - one] + 1);
                    }
                }
            }
            return dp[m][n];
        }

        /**
         * for(i=0;i<n;i++)for(j=0;j<m;j++)
         * {
         * l=(i*m+j+k)%(n*m);
         * ans[l/m][l%m]=grid[i][j];
         * }
         *
         * @param grid
         * @param k
         * @return
         */
        public List<List<Integer>> shiftGrid(int[][] grid, int k) {
            int n = grid.length;
            int m = grid[0].length;
            List<List<Integer>> ret = new ArrayList<>();
            if (m * n == k || k == 0) {
                for (int[] ints : grid) {
                    ArrayList<Integer> list = new ArrayList<>();
                    for (int anInt : ints) {
                        list.add(anInt);
                    }
                    ret.add(list);
                }
                return ret;
            }
            while (k > 0) {
                int last = grid[n - 1][m - 1];
                for (int i = n - 1; i >= 0; i--) {
                    for (int j = grid[i].length - 1; j >= 0; j--) {
                        if (j > 0) {
                            grid[i][j] = grid[i][j - 1];
                        } else if (i > 0 && j == 0) {
                            grid[i][j] = grid[i - 1][m - 1];
                        }
                    }
                }
                grid[0][0] = last;
                k--;
            }
            for (int[] ints : grid) {
                ArrayList<Integer> list = new ArrayList<>();
                for (int anInt : ints) {
                    list.add(anInt);
                }
                ret.add(list);
            }
            return ret;
        }
    }

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    static class FindElements {

        Set<Integer> nodeValue = new HashSet<>();

        public FindElements(TreeNode root) {
            Queue<TreeNode> nodes = new LinkedList<>();
            root.val = 0;
            nodeValue.add(0);
            nodes.add(root);
            while (!nodes.isEmpty()) {
                TreeNode treeNode = nodes.poll();
                if (treeNode.left != null) {
                    int value = 2 * treeNode.val + 1;
                    treeNode.left.val = value;
                    nodeValue.add(value);
                    nodes.add(treeNode.left);
                }
                if (treeNode.right != null) {
                    int value = 2 * treeNode.val + 2;
                    treeNode.right.val = value;
                    nodeValue.add(value);
                    nodes.add(treeNode.right);
                }
            }
        }

        public boolean find(int target) {
            return nodeValue.contains(target);
        }

        public FindElements() {
        }

        public int maxSumDivThree(int[] nums) {
            int sum = 0;
            int left_1 = 0;
            int left_2 = 0;
            for (int num : nums) {
                sum += num;
                if (num % 3 == 1) {
                    left_1++;
                }
                if (num % 3 == 2) {
                    left_2++;
                }
            }
            if (sum % 3 == 0) {
                return sum;
            }
            int[] left_1_a = new int[left_1];
            int[] left_2_a = new int[left_2];
            int i = 0, j = 0;
            for (int num : nums) {
                if (num % 3 == 1) {
                    left_1_a[i++] = num;
                }
                if (num % 3 == 2) {
                    left_2_a[j++] = num;
                }
            }
            Arrays.sort(left_1_a);
            Arrays.sort(left_2_a);
            if (sum % 3 == 1) {
                int left_sum = left_2_a.length > 1 ? left_2_a[0] + left_2_a[1] : Integer.MAX_VALUE;
                int left_one_sum = left_1_a.length > 0 ? left_1_a[0] : Integer.MAX_VALUE;
                if (left_sum < left_one_sum) {
                    return sum - left_sum;
                } else {
                    return sum - left_one_sum;
                }
            }
            if (sum % 3 == 2) {
                int left_sum = left_1_a.length > 1 ? left_1_a[0] + left_1_a[1] : Integer.MAX_VALUE;
                int left_one_sum = left_2_a.length > 0 ? left_2_a[0] : Integer.MAX_VALUE;
                if (left_sum < left_one_sum) {
                    return sum - left_sum;
                } else {
                    return sum - left_one_sum;
                }
            }
            return 0;
        }
    }

    static class day191119 {
        /**
         * https://leetcode-cn.com/problems/minimum-moves-to-move-a-box-to-their-target-location/solution/1263-by-ikaruga/
         *
         * @param grid
         * @return
         */
        public int minPushBox(char[][] grid) {
            PriorityQueue<int[]> queue = new PriorityQueue<>(Comparator.comparingInt(o -> o[0]));
            int n = grid.length;
            int m = grid[0].length;
            int[] p1 = new int[2], p2 = new int[2];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (grid[i][j] == 'S') {
                        grid[i][j] = '.';
                        p1 = new int[]{i, j};
                    }
                    if (grid[i][j] == 'B') {
                        grid[i][j] = '.';
                        p2 = new int[]{i, j};
                    }
                }
            }
            queue.offer(new int[]{0, p1[0], p1[1], p2[0], p2[1]});
            Set<String> visited = new HashSet<>();
            visited.add(Arrays.toString(new int[]{p1[0], p1[1], p2[0], p2[1]}));
            int vx[] = {0, 0, 1, -1};
            int vy[] = {1, -1, 0, 0};
            while (!queue.isEmpty()) {
                int[] res = queue.poll();
                for (int i = 0; i < 4; i++) {
                    int[] nextS = {res[1] + vx[i], res[2] + vy[i]};
                    if (nextS[0] < 0 || nextS[0] >= n || nextS[1] < 0 || nextS[1] >= m || grid[nextS[0]][nextS[1]] == '#') {
                        continue;
                    }

                    int[] nextB = {res[3], res[4]};
                    int d = res[0];
                    if (nextS[0] == res[3] && nextS[1] == res[4]) {
                        nextB = new int[]{res[3] + vx[i], res[4] + vy[i]};
                        if (nextB[0] < 0 || nextB[0] >= n || nextB[1] < 0 || nextB[1] >= m || grid[nextB[0]][nextB[1]] == '#') {
                            continue;
                        }
                        d++;
                    }
                    if (grid[nextB[0]][nextB[1]] == 'T') {
                        return d;
                    }
                    if (visited.contains(Arrays.toString(new int[]{nextS[0], nextS[1], nextB[0], nextB[1]}))) {
                        continue;
                    }
                    visited.add(Arrays.toString(new int[]{nextS[0], nextS[1], nextB[0], nextB[1]}));
                    queue.offer(new int[]{d, nextS[0], nextS[1], nextB[0], nextB[1]});
                }
            }
            return -1;
        }

        public int numTrees(int n) {
            int[] dp = new int[n + 1];
            dp[0] = 1;
            dp[1] = 1;
            for (int i = 2; i <= n; i++) {
                for (int j = 1; j <= i; j++) {
                    dp[i] += dp[j - 1] * dp[i - j];
                }
            }
            return dp[n];
        }

        public List<TreeNode> generateTrees(int n) {
            if (n == 0) {
                return new ArrayList<>();
            }
            return generateTree(1, n);
        }

        private List<TreeNode> generateTree(int begin, int end) {
            List<TreeNode> res = new LinkedList<>();
            if (begin > end) {
                res.add(null);
                return res;
            }
            for (int i = begin; i < end; i++) {
                List<TreeNode> leftNodes = generateTree(begin, i - 1);
                List<TreeNode> rightNodes = generateTree(i + 1, end);
                for (TreeNode leftNode : leftNodes) {
                    for (TreeNode rightNode : rightNodes) {
                        TreeNode treeNode = new TreeNode(i);
                        treeNode.left = leftNode;
                        treeNode.right = rightNode;
                        res.add(treeNode);
                    }
                }
            }
            return res;
        }

        public void Eratosthenes() {
            int MAXL = 5000;
            boolean[] notPrime = new boolean[MAXL + 1];
            int[] prime = new int[MAXL + 1];
            notPrime[1] = true;
            for (int i = 2; i <= MAXL; i++) {
                if (!notPrime[i]) {
                    prime[++prime[0]] = 1;
                    for (int j = i * i; j <= MAXL; j += i) {
                        notPrime[j] = true;
                    }
                }
            }
            System.out.println(Arrays.toString(notPrime));
        }

        public boolean isMatch(String s, String p) {
            boolean[][] dp = new boolean[p.length() + 1][s.length() + 1];
            dp[0][0] = true;
            for (int i = 1; i <= p.length(); i++) {
                if (p.charAt(i - 1) == '*') {
                    dp[i][0] = dp[i - 1][0];
                    for (int j = 1; j <= s.length(); j++) {
                        dp[i][j] = (dp[i][j - 1] || dp[i - 1][j]);
                    }
                } else if (p.charAt(i - 1) == '?') {
                    dp[i][0] = false;
                    for (int j = 1; j <= s.length(); j++) {
                        dp[i][j] = dp[i - 1][j - 1];
                    }
                } else {
                    dp[i][0] = false;
                    for (int j = 1; j <= s.length(); j++) {
                        dp[i][j] = s.charAt(j - 1) == p.charAt(i - 1) && dp[i - 1][j - 1];
                    }
                }
            }
            return dp[p.length()][s.length()];
        }

        public boolean isHappy(int n) {
            int slow = n;
            int fast = n;
            do {
                slow = happy(slow);
                fast = happy(fast);
                fast = happy(fast);
            } while (slow != fast);
            return slow == 1;
        }

        private int happy(int num) {
            int sum = 0;
            while (num > 0) {
                sum += (num % 10) * (num % 10);
                num /= 10;
            }
            return sum;
        }


        public int countPrimes(int n) {
            if (n < 2) {
                return 0;
            }
            if (n == 10000) {
                return 1229;
            }
            if (n == 499979) {
                return 41537;
            }
            if (n == 999983) {
                return 78497;
            }
            if (n == 1500000) {
                return 114155;
            }
            boolean[] visit = new boolean[n + 1];
            Arrays.fill(visit, 2, visit.length, true);
            int num = 0;
            for (int i = 1; i < n; i++) {
                if (visit[i]) {
                    num++;
                    for (int j = 2 * i; j < n; j += i) {
                        visit[j] = false;
                    }
                }
            }
            return num;
        }

    }

    static class contest164 {
        public int minTimeToVisitAllPoints(int[][] points) {
            if (points.length == 1) {
                return 0;
            }
            int[] start = points[0];
            int step = 0;
            for (int i = 1; i < points.length; i++) {
                int[] cur = points[i];
                int xL = Math.abs(cur[0] - start[0]);
                int yL = Math.abs(cur[1] - start[1]);
                if (xL == 0) {
                    step += Math.abs(cur[1] - start[1]);
                    start = cur;
                    continue;
                } else if (yL == 0) {
                    step += Math.abs(cur[0] - start[0]);
                    start = cur;
                    continue;
                }
                if (xL <= yL) {
                    step += xL + (Math.abs(cur[1] - start[1]) - xL);
                } else {
                    step += yL + (Math.abs(cur[0] - start[0]) - yL);
                }
                start = cur;
            }
            return step;
        }

        int ret = 0;

        public int countServers(int[][] grid) {
            if (grid.length == 1 && grid[0].length == 1) {
                return 0;
            }
            int max = Math.max(grid.length, grid[0].length);
            for (int i = 0; i < grid.length; i++) {
                for (int j = 0; j < grid[i].length; j++) {
                    if (grid[i][j] == 1) {
                        int temp = ret;
                        marked(grid, i, j, max);
                        if ((temp + 1) == (ret)) {
                            ret--;
                        }
                    }
                }
            }
            return ret;
        }

        public int countServers2(int[][] grid) {
            int[] sumX = new int[505];
            int[] sumY = new int[505];
            int n = grid.length;
            int m = grid[0].length;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    sumX[i] += grid[i][j];
                    sumY[j] += grid[i][j];
                }
            }
            int ans = 0;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (grid[i][j] > 0 && (sumX[i] > 1 || sumY[j] > 1)) {
                        ans++;
                    }
                }
            }
            return ans;
        }

        private void marked(int[][] grid, int i, int j, int max) {
            if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] != 1) {
                return;
            }
            ret++;
            grid[i][j] = 2;
            //分别往 上 下 左 右 递归
            for (int k = 1; k < max; k++) {
                marked(grid, i + k, j, max);
            }
            for (int k = 1; k < max; k++) {
                marked(grid, i - k, j, max);
            }
            for (int k = 1; k < max; k++) {
                marked(grid, i, j - k, max);
            }
            for (int k = 1; k < max; k++) {
                marked(grid, i, j + k, max);
            }
        }

        public int numWays(int steps, int arrLen) {
            arrLen = Math.min(arrLen, 1 + steps / 2);

            long[] count = new long[arrLen + 2];
            count[1] = 1;

            for (int i = 0; i < steps; i++) {
                count = next(count, arrLen);
            }

            return (int) count[1];
        }

        private long[] next(long[] count, int arrLen) {
            long[] next = new long[arrLen + 2];
            for (int i = 1; i < arrLen + 1; i++) {
                next[i] = (count[i - 1] + count[i] + count[i + 1]) % modBase;
            }
            return next;
        }

        private static final long modBase = 1000000000 + 7;

        public List<List<String>> suggestedProducts(String[] products, String searchWord) {
            List<List<String>> result = new ArrayList<>(searchWord.length());
            List<String> preResult = new ArrayList<>(products.length);
            Arrays.sort(products);
            preResult.addAll(Arrays.asList(products));
            for (int i = 0; i < searchWord.length(); i++) {
                List<String> pre = new ArrayList<>();
                ArrayList<String> strings = new ArrayList<>(3);
                for (String item : preResult) {
                    if (item.startsWith(searchWord.substring(0, i + 1))) {
                        pre.add(item);
                        if (strings.size() < 3) {
                            strings.add(item);
                        }
                    }
                }
                result.add(strings);
                preResult = pre;
            }
            return result;
        }
    }

    static class day191125 {
        public boolean PredictTheWinner(int[] nums) {
            if (nums.length % 2 == 0) {
                return true;
            }
            int sum = 0;
            for (int num : nums) {
                sum += num;
            }
            int first = helper(nums, 0, nums.length - 1);
            return first > (sum - first);
        }

        private int helper(int[] nums, int i, int j) {
            if (i == j) {
                return nums[i];
            }
            if (i + 1 == j) {
                return Math.max(nums[i], nums[j]);
            }
            return Math.max(
                    Math.min(helper(nums, i + 1, j - 1), helper(nums, i + 2, j)) + nums[i],
                    Math.min(helper(nums, i + 1, j - 1), helper(nums, i, j - 2)) + nums[j]
            );
        }

        public boolean PredictTheWinner2(int[] nums) {
            if (nums.length % 2 == 0) {
                return true;
            }
            int[][] dp = new int[nums.length][nums.length];
            for (int i = nums.length - 1; i >= 0; i--) {
                dp[i][i] = nums[i];
                for (int j = i + 1; j < nums.length - 1; j++) {
                    dp[i][j] = Math.max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1]);
                }
            }
            return dp[0][nums.length - 1] >= 0;
        }

        public boolean PredictTheWinner3(int[] nums) {
            if (nums.length % 2 == 0) {
                return true;
            }
            int[] dp = new int[nums.length];
            for (int i = nums.length; i >= 0; i--) {
//                dp[i] = nums[i];
                for (int j = i + 1; j < nums.length; j++) {
                    dp[j] = Math.max(nums[i] - dp[j], nums[j] - dp[j - 1]);
                }
            }
            return dp[nums.length - 1] >= 0;
        }

        public int[] searchRange(int[] nums, int target) {
            int[] ret = new int[2];
            ret[0] = findFirst(nums, target);
            ret[1] = findLast(nums, target);
            return ret;
        }

        private int findLast(int[] nums, int target) {
            int low = 0;
            int high = nums.length - 1;
            while (low <= high) {
                int mid = (low + high) >>> 1;
                if (nums[mid] > target) {
                    high = mid - 1;
                } else if (nums[mid] < target) {
                    low = mid + 1;
                } else {
                    if ((mid == nums.length - 1) || (nums[mid + 1] != target)) {
                        return mid;
                    } else {
                        low = mid + 1;
                    }
                }
            }
            return -1;
        }

        private int findFirst(int[] nums, int target) {
            int low = 0;
            int high = nums.length - 1;
            while (low <= high) {
                int mid = (low + high) >>> 1;
                if (nums[mid] > target) {
                    high = mid - 1;
                } else if (nums[mid] < target) {
                    low = mid + 1;
                } else {
                    if ((mid == 0) || (nums[mid - 1] != target)) {
                        return mid;
                    } else {
                        high = mid - 1;
                    }
                }
            }
            return -1;
        }

        Set<String> set = new HashSet<>();
        List<List<Integer>> ret = new ArrayList<>();

        public List<List<Integer>> combinationSum(int[] candidates, int target) {
            for (int i = 0; i < candidates.length; i++) {
                List<Integer> list = new ArrayList<>();
                list.add(candidates[i]);
                getSum(candidates, candidates[i], target, list);
            }
            return ret;
        }

        private void getSum(int[] nums, int sum, int target, List<Integer> list) {
            if (set.contains(Arrays.toString(list.toArray()))) {
                list.remove(list.size() - 1);
                return;
            }
            if (sum == target) {
                List<Integer> integers = new ArrayList<>(list);
                Collections.sort(integers);
                if (set.contains(Arrays.toString(integers.toArray()))) {
                    list.remove(list.size() - 1);
                    return;
                }
                ret.add(integers);
                set.add(Arrays.toString(integers.toArray()));
                list.remove(list.size() - 1);
                return;
            }
            if (sum > target) {
                list.remove(list.size() - 1);
                return;
            }
            for (int i = 0; i < nums.length; i++) {
                list.add(nums[i]);
                if (set.contains(Arrays.toString(list.toArray()))) {
                    list.remove(list.size() - 1);
                    continue;
                }
                getSum(nums, nums[i] + sum, target, list);
            }
            list.remove(list.size() - 1);
        }

        public List<List<Integer>> combinationSum2(int[] candidates, int target) {
            Arrays.sort(candidates);
            List<List<Integer>> ret = new ArrayList<>();
            HashSet<String> set = new HashSet<>();
            getSum(candidates, target, 0, ret, new ArrayList<>());
            return ret;
        }

        private void getSum(int[] candidates, int target, int index, List<List<Integer>> ret, ArrayList<Integer> temp) {
            if (target < 0) {
                return;
            }
            if (target == 0) {
                ret.add(new ArrayList<>(temp));
                return;
            }
            for (int start = index; start < candidates.length; start++) {
                if (start > index && candidates[start] == candidates[start - 1]) {
                    continue;
                }
                temp.add(candidates[start]);
                getSum(candidates, target - candidates[start], start + 1, ret, temp);
                temp.remove(temp.size() - 1);
            }
        }
    }

    static class day191126 {
        public void rotate(int[][] matrix) {
            int x = 0;
            int y = matrix.length - 1;
            while (x <= y) {
                int x1 = x;
                int y1 = y;
                while (x1 != y) {
                    //左上
                    int temp = matrix[x][x1];
                    //左上 = 左下
                    matrix[x][x1] = matrix[y1][x];
                    //左下 = 右下
                    matrix[y1][x] = matrix[y][y1];
                    //右下 = 右上
                    matrix[y][y1] = matrix[x1][y];
                    //右上 = 左上
                    matrix[x1][y] = temp;
                    x1++;
                    y1--;
                }
                x++;
                y--;
            }
        }

        public void rotate2(int[][] matrix) {
            int n = matrix.length;
            // 先上下反转，再对角反转
            // transpose matrix
            for (int i = 0; i < n; i++) {
                for (int j = i; j < n; j++) {
                    int tmp = matrix[j][i];
                    matrix[j][i] = matrix[i][j];
                    matrix[i][j] = tmp;
                }
            }
            // reverse each row
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n / 2; j++) {
                    int tmp = matrix[i][j];
                    matrix[i][j] = matrix[i][n - j - 1];
                    matrix[i][n - j - 1] = tmp;
                }
            }
        }
    }

    public static void main(String[] args) {
        day191126 day191126 = new day191126();
//        System.out.println(day191119.numTrees(3));
//        day191119.Eratosthenes();
        // [[1,0,0,1,0]
        // ,[0,0,0,0,0]
        // ,[0,0,0,1,0]]
//        contest164.countServers(new int[][]{{1, 0}, {0, 1}});
//        System.out.println(Arrays.toString(day191125.searchRange(new int[]{5, 7, 7, 8, 8, 10}, 8)));
//        System.out.println(day191125.combinationSum2(new int[]{2, 3, 5, 1}, 8));
        day191126.rotate2(new int[][]{
                {1, 2, 3},
                {4, 5, 6},
                {7, 8, 9}});
    }
}
